#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
int map[N][N];
int dis[N];
bool vis[N];
int n;
using namespace std;
int Dij(int x)
{
    memset(dis, 0x3f, sizeof(dis));
    dis[x] = 0;
    for (int i = 0; i < n; i++) {
        int pos = -1;
        for (int j = 1; j <= n; j++) {
            if ((!vis[i] && (pos == -1 || dis[i] < dis[pos]))) {
                pos = j;
            }
        }
        vis[pos] = 1;
        for (int j = 1; j <= n; j++) {
            dis[j] = min(dis[j], dis[pos] + map[pos][j]);
        }
    }
    if (dis[n] == 0x3f3f3f3f) {
        return -1;
    }
    else {
        return dis[n];
    }
}
